import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2024-12-08
 * Time: 18:06
 */
class Solution2_1 {
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length-1);
        return nums;
    }

    public void quickSort(int[] nums , int l , int r){
        if(l >= r){
            return;
        }
        // Random random = new Random();
        // int index = random.nextInt(l + (r-l+1));//随机下标
        // int key = nums[index];//随机数

        int key = nums[new Random().nextInt((r-l+1))+l];
        int left = l-1 , right = r+1 , i = l;
        while(i < right){
            if(nums[i] < key){
                swap(nums,i++,++left);
            }else if(nums[i] == key){
                i++;
            }else{
                swap(nums,i,--right);
                //i++;不能++换过来的数还是一个没有被排序的数
            }
        }
        quickSort(nums,l,left);
        quickSort(nums,right,r);
    }

    public void swap(int[] nums , int a , int b){
        int tem = nums[a];
        nums[a] = nums[b];
        nums[b] = tem;
    }
}
class Solution2 {
    public int[] sortArray(int[] nums) {
        int n = nums.length;
        for(int j = n-1 ; j > 0 ; j--){
            for(int i = 0 ; i < j ;){
                if(nums[i] > nums[i+1]){
                    swap(nums , i , i+1);
                    i++;
                }else{
                    i++;
                }
            }
        }
        return nums;
    }

    public void swap(int nums[] , int a , int b){
        int tem = nums[a];
        nums[a] = nums[b];
        nums[b] = tem;
    }

}
public class Test2 {
}
